//330. 按要求补齐数组

//给定一个已排序的正整数数组 nums，和一个正整数 n 。
//从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 
//区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出
//满足上述要求的最少需要补充的数字个数。

//思路：力扣题解评论区看到一位大神的解法
//如果我有砝码0，能称的重量为0
//再加一个砝码1，能称的重量不到2    1
//再加一个砝码2，能称的重量不到4    1    1+2
//再加一个砝码4，能称的重量不到8    1    2    1+2    4  1+4    1+2+4
//再加一个砝码8，能称的重量不到16（16以内的全都能称出来）
//因为我每次前一步已经完全覆盖[0，n),再加一个n kg的不就能覆盖[0，2n)了吗。
//同时为了加的次数最少我们才这样加，不需要1，2，3，4，5.....每种砝码都有。
//只有这样先做到局部加砝码最少，才能保证到后边n很大时加的砝码最少。

class Solution{
	public int minPatches(int[] nums,int n){
		int count=0;//用来计算缺少的砝码个数的
		long tag=1;
		int len=nums.length,index=0;
		while(tag<=n){	// 能连续覆盖的重量还没到n，有两种情况：断码(缺砝码)，或者还有砝码没加
			if(index<len&&nums[index]<=len){
				tag+=nums[index];
				index++;
	//上面判断语句可能不好理解，若现有砝码1, 4, 6, n为10，当一次循环后砝码1已计入x,x=2，但是nums[1]=4>2;
    //这说明断码了，我们需要的是重量为x=2的砝码，所以加一个，现在能称的重量就能覆盖到原来的2倍=4了（不到4）
    //然后nums[1]=4就等于4，4的砝码我们刚好有，加进来，现在能称的重量就能覆盖到原来的2倍=8了（不到8）
    //然后nums[2]=6<8，这个不是必需的砝码，加进来，现在能称的重量就能覆盖到8+6=14了（不到14）
			}else{
				tag*=2;//加一个现在刚好覆盖不到的重量的砝码，覆盖范围翻倍
				count++;//计数+1
			}
		}
	return count;
	//所以再加1个重量为2的，我们就可以最大称到13.
	}
}